package com.shangguigu.binarytree;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2019/10/28
 * @description: 赫夫曼编码原理探索和文件压缩实践(这个费事，从理解整个huffman编码到解压缩，原码反码补码。暂时了解流程。)
 * 1.定义Huffman节点（Byte data;int weight;Implement Compare）
 * 2.实现Huffman节点转换
 * 3.转换为编码表
 * 4.转换为二进制表示的字符串（补码形式！）
 * 5.虽然通过4步骤完成了二进制的字符串，但是需要转成byte[] 才能达到压缩的目的
 *
 * TODO:huffman编码方法的压缩注意：
 * 1.对于pptx文件不明显，因为已经压缩过了
 * 2.压缩如果重复数据不多，压缩不明显
 * 3.理论上可以压缩所有文件
 */
public class HuffmanCode {

	/**
	 * huffman编码表
	 */
	private Map<Byte, String> huffmanTable = new HashMap<>();

	/**
	 * 1-根据字节数组生成 HfmTreeNode 数组
	 * 1.遍历统计节点的 data 和 weight
	 * 2.生成
	 *
	 * @param bytes
	 * @return
	 */
	public List<HfmTreeNode> getNodes(byte[] bytes) {
		List<HfmTreeNode> result = new ArrayList<>();

		///1.统计 byte 及次数
		Map<Byte, Integer> map = new HashMap<>();
		for (byte item :
				bytes) {
			if (map.containsKey(item)) {
				map.put(item, map.get(item) + 1);
			} else {
				map.put(item, 1);
			}
		}

		for (Map.Entry<Byte, Integer> item :
				map.entrySet()) {
			result.add(new HfmTreeNode(item.getKey(), item.getValue()));
		}
		return result;

	}

	/**
	 * 2-获取huffman tree
	 * 1.排序
	 * 2.选取节点
	 *
	 * @return
	 */
	public HfmTreeNode getHfmTree(List<HfmTreeNode> nodes) {

		while (nodes.size() > 1) {
			///1.从小到大排序
			Collections.sort(nodes);
			///2.将倒数第二大作为左节点
			HfmTreeNode right = nodes.remove(1);
			HfmTreeNode left = nodes.remove(0);
			///3.实际中只需要用到叶子节点，所以 data 为 null
			HfmTreeNode node = new HfmTreeNode(null, left.weight + right.weight, left, right);
			nodes.add(node);
		}

		return nodes.get(0);
	}

	/**
	 * 3-获取huffman编码表(这个居然像{@link com.leetcode.binarytree.BinaryTreePaths257A})
	 * 1.编码表即存放 byte 和 前缀编码的对应关系-> Map<Byte,String>;
	 * 2.关键在于怎么取遍历获取路径(规定左走为0，右走为1)
	 */
	public Map<Byte, String> getHfmCode(HfmTreeNode node) {
		Map<Byte, String> result = new HashMap<>();
		///StringBuilder stringBuilder = new StringBuilder();
		String str = "";
		if (node.left != null) {
			///stringBuilder.append(0);
			str = "".concat("0");
			getHfmCode(result, node.left, str);
		}
		if (node.right != null) {
			///stringBuilder.append(1);
			str = "".concat("1");
			getHfmCode(result, node.right, str);
		}
		return result;
	}

	/**
	 * 将整个流程串起来，得到一个hfm字符
	 *
	 * @return
	 */
	public String getHfmString(String content) {
		byte[] bytes = content.getBytes();
		return gertHfmString(bytes);
	}

	/**
	 * 获取huffman字符串
	 *
	 * @param bytes
	 * @return
	 */
	public String gertHfmString(byte[] bytes) {
		HuffmanCode.HfmTreeNode hfmTree = getHfmTree(getNodes(bytes));
		///1.得到编码表
		Map<Byte, String> hfmCode = getHfmCode(hfmTree);
		this.huffmanTable = hfmCode;
		StringBuilder stringBuilder = new StringBuilder();
		///2.得到结果
		for (byte item :
				bytes) {
			stringBuilder.append(hfmCode.get(item));
		}
		return stringBuilder.toString();
	}

	/**
	 * 压缩
	 *
	 * @param bytes        原始从字符串得来的字节数组
	 * @param huffmanCodes huffman编码表
	 * @return 压缩后的字节数组
	 */
	public byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
		///中间状态：转为字符串
		String tempStr = gertHfmString(bytes);
		///设计到字符串循环操作就用StringBuilder吧
		///int len=(tempStr.length()+7)/8;
		StringBuilder sb = new StringBuilder(tempStr);
		///todo:不整除8的需要将结果+1。这个方法很巧了！
		int len = (sb.length() + 7) / 8;

		byte[] res = new byte[len];
		int index = 0;
		///由于八位一个字符
		int STEP_LEN = 8;
		for (int i = 0; i < sb.length(); i += STEP_LEN) {
			String tempByte = "";
			if (i + 8 < sb.length()) {
				tempByte = sb.substring(i, i + 8);
			} else {
				tempByte = sb.substring(i);
			}
			res[index++] = (byte) Integer.parseInt(tempByte);
		}
		return res;
	}

	/**
	 * 解压
	 * 思路：XXXX 貌似不是我想的这么简单！
	 * 1.将byte[] 转为 StringBuilder (1001001形式)
	 * 2.将 StringBuilder (1001001形式) 对应原字符串
	 *
	 * @return
	 */
	public String unZip() {
		//todo:
		return null;
	}

	/**
	 * 1.将byte[] 转为 StringBuilder (1001001形式)
	 * @param bytes
	 * @return
	 */
	public String getStringBuilder(byte[] bytes){
		return new String(bytes);
	}

	/**
	 *
	 * @param str
	 * @return
	 */
	public String getSourceStr(String str){
		///临时变量用于存放huffman逆向编码表-
		Map<String, Byte> tempMap=new HashMap<>();
		for (Map.Entry<Byte, String> item:
			 huffmanTable.entrySet()) {
			tempMap.put(item.getValue(),item.getKey());
		}
		StringBuilder sb=new StringBuilder();
		///需要一个指针--双指针.感觉复杂度蛮高的
		int j=1;
		for (int i = 0; i < str.length(); i++) {

		}
		return null;
	}

	/**
	 * TODO:将一个byte 转为一个二进制的字符串
	 * @param flag	是否需要补高位。true 表示需要
	 * @param b	传入的byte
	 * @return
	 */
	public String byteToBitString(boolean flag, byte b){
		///变量保存b--将b转成int
		int temp=b;
		///如果是正数就补足高位：因为 toBinaryString 对于正数只返回非0起始的数
		if (flag){
			temp|=256;
		}
		String str=Integer.toBinaryString(temp);
		if (flag){
			return str.substring(str.length() - 8);
		}else {
			return str;
		}
	}

	/**
	 * TODO:完成对压缩数据的解码
	 * 1.
	 * @param huffmanCodes	huffman编码表
	 * @param huffmanBytes	huffman编码得到的字节数组
	 * @return	就是原来字符串对应的数组
	 */
	public byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
		///1.先得到 huffmanBytes 对应的二进制字符串，形式 10111000100...
		StringBuilder stringBuilder = new StringBuilder();
		///将byte数组转成二进制字符串
		for (int i = 0; i < huffmanBytes.length; i++) {
			byte b = huffmanBytes[i];
			///判断是不是最后一个字节
			boolean flag=(i==huffmanBytes.length-1);
			stringBuilder.append(byteToBitString(!flag, b));
		}
		System.out.println(stringBuilder.toString());
		return null;
	}

	/**
	 * @param map
	 * @param node
	 * @param str
	 */
	private void getHfmCode(Map<Byte, String> map, HfmTreeNode node, String str) {
		///到达叶子节点即huffman的数据节点
		if (node.left == null && node.right == null) {
			map.put(node.data, str);
		}
		///左|右节点不为空的时候，说明有叶子节点，需要继续挖掘
		if (node.left != null) {
			String leftStr = str.concat("0");
			getHfmCode(map, node.left, leftStr);
		}
		if (node.right != null) {
			String rightStr = str.concat("1");
			getHfmCode(map, node.right, rightStr);
		}
	}


	/////////

	private byte[] huffmanZip(byte[] bytes){
		List<HfmTreeNode> nodes = getNodes(bytes);
		//根据 nodes 创建的赫夫曼树
		HfmTreeNode huffmanTreeRoot = getHfmTree(nodes);
		//对应的赫夫曼编码(根据 赫夫曼树)
		Map<Byte, String> huffmanCodes = getHfmCode(huffmanTreeRoot);
		//根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
		byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
		return huffmanCodeBytes;
	}

	//region	最后封装出来的方法

	public void zipFile(String srcFile, String dstFile){
//创建输出流
		OutputStream os = null;
		ObjectOutputStream oos = null;
		//创建文件的输入流
		FileInputStream is = null;
		try {
			//创建文件的输入流
			is = new FileInputStream(srcFile);
			//创建一个和源文件大小一样的byte[]
			byte[] b = new byte[is.available()];
			//读取文件
			is.read(b);
			//直接对源文件压缩
			byte[] huffmanBytes = huffmanZip(b);
			//创建文件的输出流, 存放压缩文件
			os = new FileOutputStream(dstFile);
			//创建一个和文件输出流关联的ObjectOutputStream
			oos = new ObjectOutputStream(os);
			//把 赫夫曼编码后的字节数组写入压缩文件
			oos.writeObject(huffmanBytes); //我们是把
			//这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
			//注意一定要把赫夫曼编码 写入压缩文件
			oos.writeObject(huffmanTable);


		}catch (Exception e) {
			// TODO: handle exception
			System.out.println(e.getMessage());
		}finally {
			try {
				is.close();
				oos.close();
				os.close();
			}catch (Exception e) {
				// TODO: handle exception
				System.out.println(e.getMessage());
			}
		}
	}

	//endregion

	/**
	 * 赫夫曼节点
	 */
	class HfmTreeNode implements Comparable<HfmTreeNode> {

		/**
		 * 字节数据
		 */
		public Byte data;
		/**
		 * 次数
		 */
		public int weight;
		/**
		 *
		 */
		public HfmTreeNode left;
		/**
		 *
		 */
		public HfmTreeNode right;

		public HfmTreeNode(Byte data, int weight) {
			this.data = data;
			this.weight = weight;
		}

		/**
		 * entire constructor
		 *
		 * @param data
		 * @param weight
		 * @param left
		 * @param right
		 */
		public HfmTreeNode(Byte data, int weight, HfmTreeNode left, HfmTreeNode right) {
			this.data = data;
			this.weight = weight;
			this.left = left;
			this.right = right;
		}

		/**
		 * 从小到大排序
		 *
		 * @param o
		 * @return
		 */
		@Override
		public int compareTo(HfmTreeNode o) {
			return this.weight - o.weight;
		}
	}

}
